53. 最大子数组和

Similar Question

Solution Tips

方案一: 贪心

贪心的思路为局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。从而推出全局最优：选取最大“连续和”

var maxSubArray = function (nums) {
    // 和 376 真的好像
    // 目前是 -2 我选 1,能让整个变得更大, 然后是 -3, 但是我不选-3就选不到4了
    // 如果当前数组是一个负数, 而下一个是正数, 那其实抛弃掉从正数开始继续构建更好
    // 很容易陷入回溯法的二元思路中, 选或者不选这个元素, 进行回溯...
    // 找反例, 有没有可能抛弃正数也能获得更大呢?
    // 99 -98 99, 感觉不可能, 那就保持正数一直遍历下去, 变为负数就切换到下一个正数
    // 那玩意全都是负数呢? 所以是遇到新的正数就重新开始
    let sum = 0;
    let max = Number.MIN_SAFE_INTEGER;
    for (let i = 0; i < nums.length; i++) {
        if (sum <= 0 && nums[i] > sum) {
            sum = nums[i];
        }
        else {
            sum += nums[i];
        }
        if (sum > max) {
            max = sum;
        }
    }

    return max;
};

方案二: 动态规划

基于方案一的思路出发, 转换为动态规划形式

确定递推公式

dp[i] 只有两个方向可以推出来：

• dp[i - 1] + nums[i]，即：nums[i] 加入当前连续子序列和
• nums[i]，即：从头开始计算当前连续子序列和

一定是取最大的，所以 dp[i] = max(dp[i - 1] + nums[i], nums[i]);

var maxSubArray = function(nums) {
    // 之前做的是贪心算法, 只要和为负数了, 遇到更大的就直接切换成新的数组
    // 现在用 dp 在做一遍
    // 1. dp[i] 表示以 i 结尾的数组的最大子数组和
    const dp = Array.from({ length: nums.length });
    dp[-1] = Number.MIN_SAFE_INTEGER;
    dp[0] = nums[0];
    let res = nums[0];

    for (let i = 1; i < nums.length; i++) {
        // if (dp[i - 1] > 0) {
        //     dp[i] = nums[i] + dp[i - 1];
        // }
        // else {
        //     dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
		// 两个分支可以简化为一条
		dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
        res = Math.max(res, dp[i]);
    }

    return res;
};
console.log(maxSubArray([-2,1,-3,4,-1,2,1,-5,4]));

方案三: 前缀和

var maxSubArray = function(nums) {
    // 子数和问题, 转化为前缀和
    const prefixSum = [];
    prefixSum[-1] = 0;
    let minPreSum = 0;
    let res = Number.MIN_SAFE_INTEGER;
    for (let i = 0; i < nums.length; i++) {
        prefixSum[i] = prefixSum[i - 1] + nums[i];
        // 最大子数组和等于 = 当前减去前面出现过的最小的前缀和
        res = Math.max(res, prefixSum[i] - minPreSum);
        minPreSum = Math.min(minPreSum, prefixSum[i]);
    }
    return res;
};